package com.offer;

/**
 * 面试题29：数组中出现次数超过一半的数字
 * 
 * 题目大致为： 数组中有一个数字出现的次数超过数组长度的一半，找出这个数字。
 * 思路：
 * 在遍历数组的过程中纪录两个量，一个是数组中的数字，一个是次数，当下一个数字和我们保存的一致时则次数加1，
 * 当不一致时次数减1，当次数为0时，重置两个量。数组中的数字为当前访问的值，次数为1。这里主要是利用了出现
 * 的次数超过了一半，其实就是超过一半数出现的次数减去其他的数出现的次数始终是大于0的
 * 
 */
public class Item29 {
	public static void main(String args[]) {
		int testArray[] = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
		System.out.println("超过一半的数字为：" + moreThanHalfNum(testArray));
	}

	public static int moreThanHalfNum(int array[]) {
		// 一种巧妙的解法
		int length = array.length;// 数组的长度
		int result = array[0];
		int times = 0;
		for (int i = 1; i < length; i++) {
			if (times == 0) {
				result = array[i];
				times = 1;
			} else if (array[i] == result) {
				times++;
			} else {
				times--;
			}
		}
		return result;
	}
}
